package niuke;

import java.util.*;

public class niuKeMain16 {
    public ListNode rotateLinkedList (ListNode head, int k) {
        // write code here
        if (head==null){
            return null;
        }
        int n=0;
        ListNode node=head;
        while (node!=null){
            n++;
            node=node.next;
        }
        k=k%n;
        ListNode[] node1=new ListNode[n];
        for (int i = 0; i < n; i++) {
            node1[i]=head;
            head=head.next;
        }
        for (int i = 0; i < k; i++) {
            ListNode node2=node1[n-1];
            for (int j = n-1; j >0; j--) {
                node1[j]=node1[j-1];
            }
            node1[0]=node2;
        }
        for (int i = 0; i < n-1; i++) {
            node1[i].next=node1[i+1];
        }
        node1[n-1].next=null;
        return node1[0];
    }
    public String removeKnums (String num, int k) {
        // write code here
        if (num==null){
            return "0";
        }
        int n=num.length();
        char ch[]=num.toCharArray();
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty()&&k>0&&stack.peek()>ch[i]){
                stack.pop();
                k--;
            }
            stack.push(ch[i]);
        }
        for (int i = 0; i < k; i++) {
            stack.pop();
        }
        StringBuffer st=new StringBuffer();
        int flag=1;
        for (Character ch1:stack) {
            if (ch1=='0'&&flag==1){
                continue;
            }
            flag=0;
            st.append(ch1);
        }
        return st.length()==0?"0":st.toString();
    }
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root==null){
            return false;
        }
        Queue<String> queue1=new LinkedList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode node=root;
        queue.add(node);
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size>0){
                TreeNode node1=queue.poll();
                if (node1!=null){
                    queue.add(node1.left);
                    queue.add(node1.right);
                    queue1.add(String.valueOf(node1.val));
                }
                else {
                    queue1.add("null");
                }
                size--;
            }
        }
        while (!queue1.isEmpty()){
           String st= queue1.poll();
           if (st.equals("null")&&queue1.size()>0&&!queue1.poll().equals("null")){
               return false;
           }
        }
        return true;
    }
    public int singleNumber (int[] nums) {
        // write code here
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int n:nums) {
            if (map.containsKey(n)){
                int value=map.get(n);
                map.put(n,value+1);
            }else {
                map.put(n,1);
            }
        }
        for (int n:nums) {
            if (map.get(n)==1){
                return n;
            }
        }
        return -1;
    }
    public ListNode sortLinkedList (ListNode head) {
        // write code here
        if (head==null){
            return null;
        }
        ListNode n1=new ListNode(-1);
        ListNode n2=new ListNode(-1);
        ListNode n3=new ListNode(-1);
        ListNode node1=n1;
        ListNode node2=n2;
        ListNode node3=n3;
        ListNode slow=head;
        ListNode fast=head.next;
        while (fast!=null&&fast.next!=null){
            node1.next=slow;
            slow=slow.next.next;
            node1=node1.next;
            node2.next=fast;
            fast=fast.next.next;
            node2=node2.next;
        }
return null;
    }
    public boolean IsContinuous(int [] numbers) {
        Arrays.sort(numbers);
        int n=numbers.length;
        int count=0;
        for (int i = 0; i < n-1; i++) {
            if (numbers[i]==0){
                count++;
            }
            else{
               if (count==4){
                   return true;
               }else {
                   if (numbers[i+1]-numbers[i]==0){
                       return false;
                   }
                   else if(numbers[i+1]-numbers[i]>1){
                       if (count>=(numbers[i+1]-numbers[i]-1)){
                           count=count-(numbers[i+1]-numbers[i]-1);
                       }
                       else {
                           return false;
                       }
                   }
               }
            }
        }
        return true;
    }
    public static void main(String[] args) {
//        StringBuffer st=new StringBuffer();
//        st.append('0');
//        st.append('1');
//        st.append('2');
//        st.append('3');
//        st.append('4');
//        st.append('5');
//        System.out.println(st.toString());
        Queue<String> queue1=new LinkedList<>();
        queue1.offer("1");
        queue1.offer("2");
        queue1.offer("3");
        queue1.offer("4");
        queue1.offer("5");
        System.out.println(queue1.poll());
    }
}
